<?php


namespace XiaoGuai\DataStructure\Huffman\HuffmanTree;

use XiaoGuai\DataStructure\Huffman\HuffmanTree\HuffmanTreeNode as Node;

class HuffmanTree
{
    public function __construct()
    {
        
    }

    /**
     * 构造哈夫曼树
     * 重复从森林中找两个权重最小的树生成新树替代之
     * @param array $weights 权重数组
     * @return array
     */
    public function createHuffmanTree($weights = [])
    {
        // 初始化,生成权重森林
        $forest = [];
        foreach ($weights as $weight) {
            $node = new Node();
            $node->weight = $weight;
            $node->parent = Node::INVALID_INDEX;
            $node->leftChild = Node::INVALID_INDEX;
            $node->rightChild = Node::INVALID_INDEX;

            $forest[] = $node;
        }

        // 重复n-1次找两最小替换
        $n = count($weights);
        for ($i = 0; $i < $n; $i++) {
            // 找到森林中的两个权重最小的树
            list($index1, $index2) = $this->getTwoMinTrees($forest);
            
            // 造新树替代
            $node = new Node();
            $node->leftChild = $index1;
            $node->rightChild = $index2;
            $node->parent = Node::INVALID_INDEX;
            $node->weight = $forest[$index1]->weight + $forest[$index2]->weight;

            // 从森林中删除子树
            $forest[$index1]->parent = $n + $i;
            $forest[$index2]->parent = $n + $i;
        }

        return $forest;
    }

    /**
     * 从森林中找到两个权重最小的树
     * @param array $forest
     * @param null $node1
     * @param null $node2
     */
    protected function getTwoMinTrees($forest = [])
    {
        // 大的权重放前面,判断是否被挤出去
        $length = 0;
        $index1 = Node::INVALID_INDEX;
        $index2 = Node::INVALID_INDEX;

        /* @var $node Node */
        foreach ($forest as $index => $node) {
            if ($node->parent != Node::INVALID_INDEX) {
                // 已经有parent,表示是子树了
                continue;
            }

            if ($length < 1) {
                $index1 = $index;
                $length++;
                continue;
            }
            $weight1 = $forest[$index1]->weight;

            if ($length < 2) {
                if ($node->weight > $weight1) {
                    // 当前weight比较大,放前面
                    $index2 = $index1;
                    $index1 = $index;
                }
                continue;
            }

            // 对比与tree的weight值
            if ($node->weight < $weight1) {
                // 将当前两个中比较大的结点挤出去,并排序两个权重,大的在前
                if ($node->weight < $forest[$index2]->weight) {
                    $index1 = $index2;
                    $index2 = $index;
                } else {
                    $index1 = $index;
                }
            }
        }

        return [$index1, $index2];
    }


    /**
     * 构造哈夫曼编码
     * 左孩子0,右孩子1,从叶子结点像根结点推即可
     * @param array $weights
     * @return array $codes 与权值及字符数组的下标一致 ["010", "1", "0110", "01110"]
     */
    public function createHuffmanCode($weights = [])
    {
        $forest = $this->createHuffmanTree($weights);

        $codes = [];
        $n = count($weights);
        for ($i = 0; $i < $n; $i++) {
            $str = "";

            /* @var $node Node  */
            $node = $forest[$i];
            while ($node->parent != Node::INVALID_INDEX) {
                // 从叶子节点寻到根结点

                /* @var $parent Node  */
                $parent = $forest[$node->parent];

                // 左孩子0,右孩子1
                if ($parent->leftChild == $i) {
                    $str = '0' . $str;
                } else {
                    $str = '1' . $str;
                }

                // 继续回溯
                $node = $node->parent;
            }
            $codes[$i] = $str;
        }

        return $codes;
    }

    /**
     * 编码哈夫曼编码的文本
     * 构造哈夫曼编码,依次编码每个字符
     * @param array $maps 字符频度数组 ["A" => 21, "B" => 12]
     * @param string $text
     * @return string
     */
    public function encodeHuffmanCode(array $maps = [], string $text = "")
    {
        // 哈夫曼编码
        $codes = $this->createHuffmanCode(array_values($maps));

        // 字符编码映射 ["A" => "1001", "B" => "1010"]
        $charMap = array_combine(array_keys($maps), $codes);

        $str = "";
        foreach (str_split($text) as $char) {
            $str .= $charMap[$char];
        }
        return $str;
    }
    
    /**
     * 解码哈夫曼编码的文本
     * 构造哈夫曼编码,从根结点开始解码,直到叶子结点时,识别为一个字符,并重复根结点到叶子结点的过程
     * @param array $maps 字符频度数组 ["A" => 21, "B" => 12]
     * @param string $bits "11010101100011110101"
     * @return string
     */
    public function decodeHuffmanCode(array $maps = [], string $bits = "")
    {
        // 哈夫曼树
        $forest = $this->createHuffmanTree(array_values($maps));

        // 哈夫曼编码
        $codes = $this->createHuffmanCode(array_values($maps));

        // 字符编码映射 ["A" => 21, "B" => 12]
        $charMap = array_combine(array_keys($maps), $codes);

        $str = "";
        $code = "";
        $bitArr = str_split($bits);
        $n = count($forest);
        /* @var $node Node */
        $node = $forest[$n - 1];

        // 从根节点开始向叶子结点遍历,遇到叶子结点即返回其字符
        for ($i = 0; $i < count($bitArr); $i++) {
            // 左孩子0,右孩子1
            if ($bitArr[$i] == '1') {
                $node = $forest[$node->rightChild];
            } else {
                $node = $forest[$node->leftChild];
            }

            // 循环直到找到叶子结点,即解析到此字符
            if ($node->leftChild == Node::INVALID_INDEX
                && $node->rightChild == Node::INVALID_INDEX
            ) {
                // 找到叶子结点, 解析到此字符
                $str .= $charMap[$code];
                // node回到根结点
                $node = $forest[$n - 1];
                // code回到根节点对应的空
                $code = "";
            }
        }

        return $str;
    }
}